/*
* 类floyd O(logk * n^3) 第k条最小边
* 
* d[k, i, j]: 从i到j只经过1~k，最短路径是多少 即从i->j, 恰好经过k条边的最短路径
* d[a+b, i, j] = d[a, i, k] + d[b, k, j] k=1~n   i-(a)->k-(b)->j


* qmi: k == 38 即 ans = (k==2)+(k==4)+(k==32)
*      
* 
*/
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
// #define ONLINE_GUDGE
using namespace std;
const int N = 1010, M = 110, INF = 0x3f3f3f3f;

int k, n, m, S, E; // S -> E
int g[N][N];
int res[N][N];
map<int,int> id; // 离散化存储点，用于存储唯一点和边的最小值
int temp[N][N]; // 记录上一轮矩阵乘法的结果

// void AddEdge(int a, int b, int c)
// { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; }


void mul(int c[][N],int a[][N],int b[][N]) // 类floyd
{
    memset(temp,0x3f,sizeof temp);
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                temp[i][j]=min(temp[i][j],a[i][k]+b[k][j]); // temp = a[][] * b[][] temp永远存在
    memcpy(c,temp,sizeof temp); // temp -> c
}

void qmi()
{
    memset(res, 0x3f, sizeof res);
    for(int i = 1; i <= n; i++) res[i][i] = 0; // i->i经过0条边

    while(k)
    {
        if(k & 1) mul(res, res, g); // res=res*g;根据k决定是否用当前g的结果去更新res
        mul(g, g, g); // g = g*g
        k >>= 1;
    }

}

signed main()
{
    #ifdef ONLINE_JUDGE

    #else
        freopen("./in.txt", "r", stdin);
    #endif

    ios::sync_with_stdio(0); cin.tie(0);

    cin >> k >> m >> S >> E;
    
    memset(g, INF, sizeof g);
    // 此处不做g[i][i] = 0 的原因: 1->2->1是两条边

    if(!id.count(S)) id[S]=++n;
    if(!id.count(E)) id[E]=++n;
    S=id[S],E=id[E];
    while(m--)
    {
        int a,b,c; cin >> c >> a >> b;
        if(!id.count(a)) id[a]=++n; 
        if(!id.count(b)) id[b]=++n;
        a=id[a],b=id[b];
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    qmi();
    cout<< res[S][E] <<endl;
    return 0; 
}

